#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>


// FUNCTION: 定义动态数组
typedef int ElemType;

typedef struct {
	ElemType *elem;//存储元素的起始地址
	int TableLen;//元素个数
} SSTable;


// FUNCTION: 随机数生成
void ST_Init(SSTable &ST, int len) {
	// NOTE: 变量初始化
	// STEP: 多申请了一个位置,为了存哨兵
	ST.TableLen = len + 1;

	// STEP: 申请动态数组实际空间
	ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.TableLen);

	// STEP: 存放赋值变量是的索引
	int i;


	// NOTE: 生成随机数
	srand(time(NULL));


	// NOTE: 将数据存储到数组中
	// HINT: 为啥这里零号位置也存放了随机了数据？是为折半查找服务的。
	for (i = 0; i < ST.TableLen; i++) {
		ST.elem[i] = rand() % 100;
	}
}


// FUNCTION: 输出数组中全部元素
void ST_print(SSTable ST) {
	for (int i = 0; i < ST.TableLen; i++) {
		printf("%3d", ST.elem[i]);
	}

	printf("\n");
}


// FUNCTION: 交换数组元素
void swap(ElemType &a, ElemType &b) {
	ElemType tmp;
	tmp = a;
	a = b;
	b = tmp;
}

// FUNCTION: 简单选择排序
void Select_Sort(ElemType arr[], int n) {
	// NOTE: 临时变量声明
	// HINT: i用于记录待排序列的起始位置。min用于记录待排序列中，最小的元素索引
	int i, j, min;

	// NOTE: 总共会执行n-1次循环
	for (i = 0; i < n - 1; ++i) {
		// STEP: 初始化最小元素位置，默认是待排序列的第一个元素
		min = i;

		// STEP: 遍历待排序列，寻找最小值
		for (j = i + 1; j < n; ++j) {
			// 更新最小元素的索引值
			if (arr[j] < arr[min])
				min = j;
		}

		// STEP: 将本轮寻找到的最小元素插入待排序列的第一个元素位置。（除非，这个元素本身就是待排序列第一个元素）
		if (min != i) {
			swap(arr[i], arr[min]);
		}
	}
}


int main() {
	setbuf(stdout, NULL);


	// NOTE: Variable declaration
	// STEP: 声明动态数组
	SSTable ST;

	// STEP: 声明一组数
	ElemType A[10] = {64, 94, 95, 79, 69, 84, 18, 22, 12, 78};


	// NOTE: 数组元素赋值
	// HINT: 实际申请了11个元素空间
	ST_Init(ST, 10);
	memcpy(ST.elem, A, sizeof(A));

	printf("Original sequence is: ");
	ST_print(ST);


	// NOTE: 简单选择排序
	Select_Sort(ST.elem, 10);

	return 0;
}